package mess;

public class LeeCode_74 {
    public static void main(String[] args) {
        int[][] matrix = new int[][]{{1,3,5,7},{10,11,16,20},{23,30,34,50}};
        System.out.println(searchMatrix(matrix, 11));
    }
    private static boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int start = 0;
        int end = m - 1;

        while (start < end) {
            int mid = (start + end) / 2;
            if (matrix[mid][0] > target) {
                end = mid - 1;
            } else if (matrix[mid][0] < target) {
                start = mid + 1;
            } else
                return true;
        }
        if (start - 1 >= 0) {
            for (int i = 0; i < n; i++) {
                if (matrix[start - 1][i] == target) {
                    return true;
                } else if (matrix[start - 1][i] > target)
                    break;
            }
        }
        if (start >= 0) {
            for (int i = 0; i < n; i++) {
                if (matrix[start][i] == target) {
                    return true;
                } else if (matrix[start][i] > target)
                    break;
            }
        }
        if (start + 1 < m) {
            for (int i = 0; i < n; i++) {
                if (matrix[start + 1][i] == target) {
                    return true;
                } else if (matrix[start + 1][i] > target)
                    break;
            }
        }
        return false;
    }
}
